#include <unordered_map>
#include <list>

class LRUCache {

struct Node {
        int key;
        int value;
    };

  private:
    int capacity;
    /**
     * key是cache的key
     * value -> list iterator，也就是链表节点的迭代器
    */
    std::unordered_map<int, std::list<Node>::iterator> data_map;
    std::list<Node> data_list;

  public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
		auto it = data_map.find(key);
		if (it == data_map.end()) {
			return -1;
		}
		auto node = it->second;
		data_list.push_front(*node);
		data_list.erase(node);
		data_map[key] = data_list.begin();
		return data_list.begin()->value;
	}

	void set(int key, int value) {
		auto it = data_map.find(key);
		if (it != data_map.end()) {
			auto node = it->second;
            node->value = value;
			data_list.push_front(*node);
			data_list.erase(node);
			data_map[key] = data_list.begin();
			return;
		}
		if (data_map.size() == capacity) {
			data_map.erase(data_list.back().key);
			data_list.pop_back();
		}
		data_list.push_front({key, value});
		data_map[key] = data_list.begin();
	}
 
 /// 用splice方法把节点移动到首位 /////////////////////////////////
 int get(int key) {
    auto it = data_map.find(key);
    if (it == data_map.end()) {
        return -1;
    }
    data_list.splice(data_list.begin(), data_list, it->second);
    return it->second->value;
 }
 
 void set(int key, int value) {
    auto it = data_map.find(key);
    if (it != data_map.end()) {
        it->second->value = value;
        data_list.splice(data_list.begin(), data_list, it->second);
        return;
    }
    if (data_map.size() == capacity) {
        data_map.erase(data_list.back().key);
        data_list.pop_back();
    }
    data_list.push_front({key, value});
    data_map[key] = data_list.begin();
 }
};